
Virtual instructors are conversational agents that help a user
perform a task. These agents can be useful for many purposes, such as 
language learning~\cite{nunan04}, training in simulated environments~\cite{Lane2009}
and entertainment~\cite{Dignum2012,jan09}. In order to guide a user while performing a
task, an effective instructor knows how to describe what needs to be done in a way 
that accounts for the nuances of the virtual environment and that 
is good enough to engage the trainee or the gamer in the activity. A major bottleneck in creating and deploying such agents is that the requisite
knowledge of these agents needs to be authored manually. Nowadays, most conversational agents require
either extensive rule writing~\cite{LarssonTraum00}, or extensive manual corpus annotations~\cite{rieser10}, both of which entail a high cost in the development of a conversational agent
for a new domain. We envisage a virtual instructor that observes a human instructor and a human trainee
completing a task, and then is able to give instructions on that task. 
In this paper, we present a novel method for deploying such virtual instructors
that learn from automatically annotated human-human interactions. We propose an algorithm that, 
when given a corpus of interactions between a human instructor and a real user, 
automatically annotates it using a planner and generates an instructor that
robustly helps a user achieve the task at hand. 
 
%There are two main approaches towards automatically producing natural language instructions. One is the selection approach, in which the task is to pick the appropriate output from a corpus of possible outputs. The other is the generation approach, in which the output is dynamically assembled using some composition procedure, e.g. grammar rules. Our method falls into the generation by selection paradigm. 
 
The article proceeds as follows. In Section~\ref{sec:previous-work} we review existing approaches to generating natural language utterances for conversational agents. Section~\ref{sec:algorithm} presents the two phases of our algorithm, namely automatic annotation and generation by selection. In Section~\ref{sec:corpus} we introduce a treasure hunt task that may occur in different virtual worlds. In Section~\ref{sec:case-study} we describe how to generate an instructor in those virtual worlds and we present a fragment of an interaction with one of the the virtual instructors generated. In Section~\ref{sec:evaluation} we present the results obtained when evaluating our virtual instructor in the international shared-task known as the GIVE Challenge~\cite{KolStrGarByrCasDalMooObe10}. Finally, in Section~\ref{sec:discussion} we discuss
how our method compares to previous work in terms of development cost, naturalness, and domain independence.

